1. Field of the Invention
This invention relates to a method for testing and, if necessary, validating primitives of a real-time executive, i.e. a software, hardware and/or microprogrammed device, capable of executing several tasks on a processor designed to execute just one task at a time.
2. Description of the Prior Art
It is of interest, on the one hand, to firms who design and develop real-time executives such as the constructors of computers and microprocessors, constructors of real-time language compilers, manufacturers of computer systems or industries developing real-time applications with their own executives and, on the other hand, to industries developing real-time applications notably in the following fields: aeronautics, space, nuclear sector, railways, medicine, robotics, etc.
In the first case, these firms need to validate the product before marketing it. In the second case, these firms need to assess and verify the operating of the executives proposed on the market in order to choose the must trustworthy and the best suited to their needs.
It is recalled that each task of a real-time executive can be assimilated to a thread of control which performs on the processor while using all the resources of the machine required for execution: registers, memories, peripherals, execution time, . . .
The tasks are, theoretically, independent. They can become synchronized, communicate or exclude each other depending on the mechanisms proposed by the executive. When the tasks are implanted in a single physical processor, they are in fact run in pseudo-parallel as the processor can only execute one instruction at the time.
There is synchronization between two tasks A and B, when task A is waiting (to continue execution) for task B to free it, whence a notion of order of execution of the tasks with regard to one another. The typical diagram is that of producer/consumer where the consuming task is waiting (to consume) for the producing task to have produced.
There is communication between two tasks A and B when task A uses data created by task B. The typical diagram is also that of producer/consumer where the consuming task is waiting (to consume) for the producing task to have produced.
There is exclusion between two tasks A and B when task A is not authorized to use a resource at the same time as task B. Task A must therefore wait until task B is no longer using the resource in order to be able to use it.
A task can be put in different statuses, such as, e.g.:
--"Dead task" status (known to the application but without any connection with the launching context): in the event of a serious anomaly, one or more tasks may find themselves unable to perform any more. They are then put into the "dead" state and are no longer managed. PA0 --"Dormant task" status. In this state, which is that of a task having completed performance or that has just been initialized, the task has all the parameters required to start its application. PA0 --"Eligible task" status in which the task is awaiting a processor resource and can run as soon as the scheduler decides to allocate the processor to it. PA0 --"Elected task" status which is that of a task having gained possession of the processor by moving from the "eligible" state to the "elected" state. PA0 --"Suspended task" status is that of an elected task having encountered an unfulfilled condition, this task moving into the eligible state when this condition is fulfilled. PA0 --a set of concurrent tasks, based on a same model and only differing from one another by way of their static context (designation, priority), each of these concurrent tasks being capable of performing a randomly determined sequence of actions of two types (i.e. actions generating a progression in the operating of the task and actions consisting in standbys); PA0 --a driver task which organizes the running of the concurrent tasks and which more particularly regulates the launching of the concurrent tasks, activates the operating sequence and detects completion thereof; and PA0 --an internal resource server task, such as a random number distributor. PA0 --determination of the respective priorities of the tasks, so as to spread their activity over time and create a maximum number of different preemption cases, PA0 --a prior phase comprising: PA0 --a succession of operation phases during each of which the driver task runs the concurrent tasks through a same operating sequence, this phase comprising:
In respect of the last status, the task can be on standby for an event if it farmed out an operation to an other task of the system and is awaiting completion of the latter. It can be awaiting a resource, in the general sense, if, in order to continue, it requires a piece of hardware or software that is unavailable.
It is therefore clear that the different tasks of an executive are not usually completely independent and sometimes need to become synchronized, to communicate data with one another and to gain access to resources that cannot be shared.
For instance, a task may be preempted to the benefit of another task depending on the criteria selected by the scheduler. If, in the course of execution, the task encounters an unconditional suspension primitive or an unfulfilled condition upon, in particular, a delay, a write operation in a full mailbox, a read operation in an empty mailbox, or upon occurrence of an event, it abandons the processor to another task.
In order to take these particularities into account and to enable such an operating sequence, the executive offers (the programmer) a set of synchronization, communication and resource-sharing primitives. Utilization of these primitives solely in the necessary parts of the multi-task application enables the different tasks to perform asynchronously with regard to one another.
It is within this asynchronism that the problem of validating real-time applications is to be found, and consequently that of validating the executives themselves.
Contrary to a synchronous operation, a program operating asynchronously by means of the tasks composing it, requires an uncountable number of states (at least from the human point of view), as a result of which proof of the coherence of these states cannot be established.
This is notably due to the fact that during production of a program, at each point of the program, the programmer masters the state in which he is and determines the following state as a function of the instruction that will be implemented. This reasoning is applied from the first to the last instruction of the program by determining the program input data and therefore enables the expected results to be forecast.
The state of the program is more or less represented by the value of each of its variables at a given moment and in a given place (respectively indicated by the internal clock and by the instruction counter).
When the program has several tasks, the reasoning can be applied to each of the tasks provided the task changes are mastered in space and in time by the programmer. If this condition is no longer fulfilled, the programmer can no longer determine the exact chaining of the states of his program.
The program is then referred to as non-deterministic (i.e. requiring an infinite number of states).
In fact, task changes are usually mastered when they take place at privileged points of the program, typically when a primitive of the executive is called. The executive is then deemed "non-preemptive".
It so happens that most real-time executives are preemptive and do not enable theses changes to be mastered, and that the approach used by the programmer to validate deterministic software is only partially applicable to the validating of non-deterministic software.